import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/15 15:42
 * @description 滑动窗口
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.minWindow("ADOBECODEBANC", "ABC");
    }
    public String minWindow(String s, String t) {
        int m = s.length(), n = t.length();
        if (m < n) {
            return "";
        }
        int[] origin = new int[128];
        for (char ch: t.toCharArray()) {
            origin[ch]++;
        }
        int[] cnt = new int[128];
        // 使用双端队列存储s中属于t字符下标
        Deque<Integer> deque = new LinkedList<>();
        int left = 0, right = 0;
        String ans = "";
        boolean first = true;
        while (right < m) {
            char ch = s.charAt(right);
            if (origin[ch] >= 1) {
                // 在t中出现，那么计数 + 1，并且加入双端队列中
                cnt[ch]++;
                deque.offer(right);
            }
            // 检查是否cnt是否全为0
            while (!deque.isEmpty() && check(cnt, origin)) {
                left = deque.peekFirst();
                right = deque.peekLast();
                String temp = s.substring(left, right + 1);
                if (first) {
                    ans = temp;
                    first = false;
                }else if (temp.length() < ans.length()){
                    ans = temp;
                }
                cnt[s.charAt(deque.pollFirst())]--;
            }
            right++;
        }
        return ans;
    }
    public boolean check(int[] cnt, int[] origin) {
        for (int i = 0; i < 128; i++) {
            if (cnt[i] < origin[i]) {
                return false;
            }
        }
        return true;
    }
}
